The present invention relates in general to multi-processor computer system operation and more particularly to a method and system for using high count invalidate acknowledgements in distributed shared memory systems.
In a shared-memory multiprocessor computer system with per-processor caches, it is desirable for hardware to keep the caches coherent. This means that when one or more processors have a copy of a block or line of memory and one of the processors performs a write to that line, the cached copies must either be updated or invalidated.
Computer systems use memory directories that are associated with main memory. In large systems, memory, and thus the directories, may be physically distributed throughout the system. The directory associated with a region of memory keeps track of which processors, if any, have copies of memory lines in that region. When a write occurs to a line, the directory is consulted, and updates or invalidates are sent to any processors that have a copy of the line.
A large computer system is conventionally implemented with a large number of processors accessed through node controllers at node locations. The node controllers include the memory directories employing coarse directory protocols. A basic problem with memory directories is that the required storage does not scale well. Coarse directory protocols provide a technique that represents each processor in the computer system by saving space in the memory directory. Space is saved by grouping node controllers and associated processors that share information in memory. When it becomes necessary to invalidate all nodes with a shared copy of a cache line, invalidate commands are sent to all of the nodes within a group that includes the node that contains the shared copy of the memory. Typically, each node processes the invalidation command and sends an acknowledgment message back to the node that originated the invalidation command. Since full operation of the computer system does not continue until all expected acknowledgment messages are received, each node in a group must be present and operational for the computer system to work effectively. However, there may be situations where certain nodes of a group may not be present, may be in a failure state or simply may not share the line.
One way to reduce directory overhead is to limit the size of the directory entries such that an entry cannot represent any arbitrary set of processors in the system. The system is then either prohibited from allowing non-representable sets of processors to cache a line concurrently (by, say, invalidating the copies of certain processors when other processors obtain a copy of the line), or, more preferably, when a non-representable set of sharing processors occurs, the directory entry is set to represent some superset of the sharing processors. Then when the line is written, an invalidation or update message is sent to the superset of processors caching the line.
A goal of a directory structure for a large multiprocessor system is to use a modest number of bits in a directory entry, yet minimize the number of xe2x80x9cspuriousxe2x80x9d invalidation messages that must be sent when a line is written. That is, keep the superset as close to the size of the actual set of sharers as possible.
At one end of the spectrum is a full broadcast mechanism. In this scheme, as soon as a line becomes cached by any processor (or perhaps only when it is cached by more than one processor), the state of the corresponding directory is set to indicate that a broadcast is necessary. When the line is written, invalidations are sent to all processors in the system. This mechanism minimizes the number of bits needed in the directory entry, but maximizes spurious invalidations.
At the other end of the spectrum is the full bit-vector mechanism described above, in which a directory entry includes a bit for each processor in the system. This maximizes directory storage overhead, but eliminates spurious invalidations. The storage overhead for this scheme is unacceptable for large systems.
A reasonable middle ground is a xe2x80x9ccoarse-vectorxe2x80x9d directory structure like the one used in the Origin 2000 manufactured by Silicon Graphics In. of Mountain View, Calif. The directory structure in the Origin 2000 includes a bit vector of size v in the directory entries (where v=32). Each bit represents one or more processor nodes in the system. For systems with thirty-two or fewer nodes, this size bit vector acts like a full bit vector. For larger numbers of nodes, however, the vector can become xe2x80x9ccoarsexe2x80x9d. When the set of processor nodes sharing a line is contained within an aligned block of consecutive processor nodes, then the bit vector can still be used as a full bit vector, with another small field in the directory entry specifying the block of processor nodes the vector represents. Processor nodes will typically contain one or more processors. In the Origin 2000, each processor node includes two processors.
When the set of processor nodes expands beyond an aligned block of v processor nodes, however, the meaning of the bits in the vector is changed (this is recorded in the state information in the entry). For N-processor-node systems, each bit in the vector now represents N/v processor nodes. For example, in a 512-processor node system with a 32-bit vector, each bit in the vector represents sixteen processor nodes. For every processor node caching the line, the bit representing the set of processor nodes containing that processor node would be set. When the line is written, for each bit that is set in the coarse vector, invalidation messages are sent to the corresponding set of N/v processor nodes. In most cases, this will cause invalidations to be sent to some processor nodes that do not have a copy of the line (spurious invalidates).
Another way of compacting directory entries, in contrast to the single bit vector approach discussed above, is a multi-dimensional directory structure approach which uses two or more bit vectors to track each processor node. Such an approach is described in U.S. patent application Ser. No. 08/971,184, filed Nov. 17, 1997, now pending, entitled Multi-Dimensional Cache Coherence Directory Structure, the entire disclosure of which is incorporated herein by reference. In the multi-dimensional approach, each processor node is represented by a bit in each of the two or more bit vectors.
For example, for a system with n vectors as each processor obtains a copy of a shared line, the bits corresponding to that processor are set in each of the n vectors of the associated directory entry. If nxe2x88x921 of the vectors have only a single bit set, then the pointer information remains exact. If more than one bit is set in at least two of the fields, however, then the pointer information can become inexact, or approximate. As a result, in addition to invalidation messages being sent to shared processor nodes reading the messages, spurious invalidation messages are sent to alias processor nodes (i.e., processors the system initially interprets as sharing a line of memory that in reality do not share the line and indeed may not even exist) not needing the messages. As the number of alias processor nodes increases, determining the actual processors needing the invalidation messages becomes more cumbersome.
Typical computer systems merely allowed the problem of sending invalidation messages to non-existent nodes to occur or simply wasted directory space to handle the problem. Therefore, it is desirable to provide a technique to process invalidation commands for nodes with alias processors.
One method of handling invalidation requests to processors not present or operational in a computer system is described in U.S. patent application Ser. No. 09/410,139, filed Sep. 30, 1999, now pending, entitled Method and Apparatus for Handling Invalidation Requests to Processors Not Present in a Computer System, the entire disclosure of which is incorporated by reference herein. The method disclosed in U.S. application Ser. No. 09/410,139 includes receiving an invalidation request and identities of processors affected by the invalidation request. A determination is made as to which processors are currently present in the computer system and which processors are currently not present in the computer system. Invalidation messages are generated and transferred to processors determined to be present in the computer system. Acknowledgment messages are returned from processors that received and processed their respective invalidation message. Acknowledgment messages are generated and returned for those processors determined not to be present in the computer system. However, as the format of the sharing vectors becomes more complex and the number of alias processors increases, it becomes overly difficult to convert into a count the invalidation messages necessary in the same time that other directory calculations are taking place.
From the foregoing, it may be appreciated that a need has arisen for a technique to handle invalidation requests to processors that do not share the line being invalidated. In accordance with the present invention, a method and system for handling invalidation requests to alias processors not sharing the line are provided that substantially eliminate or reduce disadvantages and problems associated with conventional computer system operation.
According to an embodiment of the present invention there is provided a multiprocessor computer system that includes a method and system of handling invalidation requests to a plurality of alias processors not sharing a line of memory in a computer system. Invalidation herein means and includes invalidation and updating and thus the present invention as claimed includes invalidate-based coherence protocols as well as update-based protocols. A memory directory interface unit receives an invalidation request for a shared line of memory shared in a plurality of sharing processors. A superset of processors in the computer system that includes each of the sharing processors is determined that includes at least one alias processor not sharing the shared line of memory. An invalidation message is transmitted to each processor in the superset of processors. The number Na of alias processors in the superset of processors is determined and a superacknowledgement message is provided that is equivalent to acknowledging receipt of Na invalidation messages. A number of messages may make up the superacknowledgement message used to acknowledge receipt of the Na invalidation messages. In the sense that the alias processors never actually receive the invalidation messages, the superacknowledgement message simulates acknowledgement.
In an aspect of the present invention, the computer system is designed to include a maximum number M of processors and the number of processors in the superset of processors is less than M. The requester receives an acknowledgement message from each of the sharing processors.
In a further aspect of the present invention, the number Na of alias processors in the superset of processors is determined subsequent to transmitting an invalidation message to each processor in the superset of processors.
In another aspect of the present invention, at least two-bit vectors (i.e., at least a pair of bit-vectors) are used to represent processors in a vector matrix in which identification of at least two of the sharing processors in the vector matrix causes the identification of at least one of the alias processors in the vector matrix and wherein the superset of processors is determined to be the sharing processors and alias processor identified in the vector matrix.
In another aspect of the present invention, a system for handling invalidation requests to a plurality of alias processors not sharing a line of memory is provided that includes a memory directory interface unit operable to control access to and data manipulation for a memory and a processor interface unit operable to generate an invalidation request in response to data manipulation in the memory. The processor interface unit is operable to provide the invalidation request to the memory directory interface unit. The memory directory interface unit is operable to indicate a superset of processors in the computer system that may be affected by the invalidation request and subsequently identify the number of alias processors included in the superset of processors. The memory directory interface unit is also operable to generate a superacknowledgement message acknowledging receipt of the number of invalidation messages transmitted to alias processors included in the superset of processors.
In a further aspect of the present invention, a local block unit is operable to generate an invalidation message for the superset of processors. The local block unit transfers the invalidation messages to their respective processors, the processor interface unit operable to receive acknowledgment messages from the processors sharing the line of memory in response to processing of the associated invalidation message. The local block unit transfers the acknowledgment messages to the processor interface unit.
In yet another aspect of the present invention, at least two bit vectors are used to represent processors in a vector matrix in which identification of at least two of the sharing processors in the vector matrix causes the identification of at least one of the alias processors in the vector matrix. The system is configured to set the superset of processors as the sharing processors and alias processor identified in the vector matrix.
In a further aspect of the present invention, the bit vectors include a 2-bit vector, an 8-bit vector and a 16-bit vector defined by an 8-bit field operable to access 256 processor nodes identified in the vector matrix.
In another aspect of the present invention, the system is configured to include a maximum number M of processors and the system is configured to set the number of processors in the superset of processors to be less than M.
In another aspect of the present invention, the alias processors include phantom processors, i.e., the processor identified in the vector matrix either does not exist or is not operable.
Other technical advantages may be readily apparent to those skilled in the art from the following figures, description, and claims.